function Rectangle(n) {
  this.n = n;
  this.nSquared = Math.pow(n, 2);
  this.rectangle = [];
  this.gcds = [];
  this.distances = [];
  this.dNum = 0;

  var gcd = function (a,b) { if(b===0) return a; else return gcd(b, a%b);}
  var distanceSquared = function(a,b) { return Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2); }

  this._calcD = function() {
    this.dNum = 0;
    for (var i = 0; i < this.nSquared - 1; ++i) {
      var a = this.rectangle[i];
      for (var j = i + 1; j < this.nSquared; ++j) {
        var b = this.rectangle[j];
        var g = this.gcds[a - 1][b - 1];
        var ds = this.distances[i][j];
        var d = g * ds;
        this.dNum += d;
      }
    }
  }

  //create unit rectangle
  for (var i = 0; i < this.nSquared; this.rectangle[i] = ++i);

  //create GCD lookup
  for (var i = 0; i < this.nSquared; ++i) {
    this.gcds[i] = [];

    for (var j = 0; j < this.nSquared; ++j) {
      this.gcds[i][j] = gcd(i + 1, j + 1);
    }
  }

  //create distance^2 lookup
  for (var i = 0; i < this.nSquared; ++i) {
    this.distances[i] = [];

    for (var j = 0; j < this.nSquared; ++j) {
      this.distances[i][j] = distanceSquared({x: Math.floor(i / this.n), y: i % this.n}, {x: Math.floor(j / this.n), y: j % this.n});
    }
  }

  //initialize dNum
  this._calcD();



  this._swap = function(a, b) {
    var aVal = this.rectangle[a];
    var bVal = this.rectangle[b];

    for (var i = 0; i < this.nSquared; ++i) {
      var current = this.rectangle[i];
      this.dNum -= (this.gcds[aVal - 1][current - 1] * this.distances[a][i]) + (this.gcds[bVal - 1][current - 1] * this.distances[b][i]);
    }

    var temp = this.rectangle[a];
    this.rectangle[a] = this.rectangle[b];
    this.rectangle[b] = temp;

    for (var i = 0; i < this.nSquared; ++i) {
      var current = this.rectangle[i];
      this.dNum += (this.gcds[aVal - 1][current - 1] * this.distances[b][i]) + (this.gcds[bVal - 1][current - 1] * this.distances[a][i]);
    }
  }



  this.greedy1 = function(isBetter) {
    //make the best possible max move for each value i.e., best swap involving 1.
    var foundBetter = false;
    
    do {
      foundBetter = false;
      for (var j = 1; j <= this.nSquared; ++j) {
        var oneLoc = -1;
        for (var oneLoc = 0; this.rectangle[oneLoc] !== j; ++oneLoc);

        var curBest = this.dNum;
        var curBestIdx = -1;

        for (var i = 0; i < this.nSquared; ++i) {
          if (i === oneLoc) continue;

          this._swap(oneLoc, i);
          if (isBetter(this.dNum, curBest)) {
            curBestIdx = i;
            curBest = this.dNum;
          }
          this._swap(oneLoc, i);
        }

        if (curBestIdx !== -1) {
          this._swap(oneLoc, curBestIdx);
          foundBetter = true;
        }
      }
    } while (foundBetter);
  }



  this.greedyMax2 = function() {
    //make the best possible max move. i.e., check every swap until you cannot make a better move (or you start looping)
  }



  this.greedy3 = function(isBetter) {
    //make best move for each index in this.rectangle until you cannot make a better move
    var curBest = this.dNum;
    var foundBetter = false;

    do {
      foundBetter = false;
      for (var i = 0; i < this.nSquared - 1; ++i) {
        for (var j = i + 1; j < this.nSquared; ++j) {
          this._swap(i, j);
          if (isBetter(this.dNum, curBest)) {
            curBest = this.dNum;
            foundBetter = true;
          } else {
            this._swap(i, j);
          }
        }
      }
    } while (foundBetter) ;
  }



  this.randomize = function() {
    this.rectangle = [];

    for (var i = 1; i <= this.nSquared; ++i) {
      var randPos = -1;
      do {
        randPos = Math.floor(Math.random() * this.nSquared);
      } while (this.rectangle[randPos] !== undefined);
      this.rectangle[randPos] = i;
    }

    this._calcD();
  }



  this.randomSwap = function() {
    var rand1, rand2;
    var rand1 = Math.floor(Math.random() * this.nSquared);
    do {
      var rand2 = Math.floor(Math.random() * this.nSquared);
    } while (rand1 === rand2);
    this._swap(rand1, rand2);
  }



  this.toString = function() {
    //TODO string concatenation is slow, but how often do I need to write improved scores?
    var result = '';

    for (var i = 0; i < this.n; ++i) {
      if (i > 0) {
        result += ',';
      }
      result += '('
      for (var j = 0; j < this.n; ++j) {
        if (j > 0) {
          result += ','
        }
        result += this.rectangle[this.n * i + j];
      }
      result += ')';
    }

    return result;
  }
}



onmessage = function(oEvent) {
  var oRectangle = new Rectangle(oEvent.data.n);
  var min = oEvent.data.minD;
  var max = oEvent.data.maxD;
  var progress = 0;
  var lastProgressReport = -1;

  while (true) {
    ++progress;
    if (lastProgressReport < Date.now() - 1000) {
      lastProgressReport = Date.now();
      postMessage({ n: oEvent.data.n, type: 'PROGRESS', progress: progress });
    }
    oRectangle.randomize();

    oRectangle.greedy1(function(val, best) { return val < best; });  //min
    if (oRectangle.dNum < min) {
      min = oRectangle.dNum;
      postMessage({ n: oEvent.data.n, square: oRectangle.toString(), type: 'MIN', dn: oRectangle.dNum });
    }

    oRectangle.greedy1(function(val, best) { return val > best; });  //max
    if (oRectangle.dNum > max) {
      max = oRectangle.dNum;
      postMessage({ n: oEvent.data.n, square: oRectangle.toString(), type: 'MAX', dn: oRectangle.dNum });
    }
  }
}
